package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _110建立四叉树
 * @description
 * @date 2023/08/13 10:43
 * <p>
 * ******************************************************
 */
public class _110建立四叉树 {

    public Node construct(int[][] grid) {
        int n = grid.length;
        return dfs(grid, 0, 0, n - 1, n - 1);
    }

    private Node dfs(int[][] grid, int a, int b, int c, int d) {
        int n = grid.length;
        boolean ok = true;
        int t = grid[a][b];
        // 判断该区域里面的值是否都一样，都一样则该节点可以是叶子节点
        for (int i = a; i <= c && ok; i++) {
            for (int j = b; j <= d && ok; j++) {
                if (grid[i][j] != t) ok = false;
            }
        }
        if (ok) return new Node(t == 1, true);
        Node root = new Node(t == 1, false);
        int dx = c - a + 1, dy = d - b + 1;
        root.topLeft = dfs(grid, a, b, a + dx / 2 - 1, b + dy / 2 - 1);
        root.topRight = dfs(grid, a, b + dy / 2, a + dx / 2 - 1, d);
        root.bottomLeft = dfs(grid, a + dx / 2, b, c, b + dy / 2 - 1);
        root.bottomRight = dfs(grid, a + dx / 2, b + dy / 2, c, d);
        return root;
    }


    class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;


        public Node() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = topLeft;
            this.topRight = topRight;
            this.bottomLeft = bottomLeft;
            this.bottomRight = bottomRight;
        }
    }

}
